package com.example.demo.leetcode.zuocheng.graph;

/**
 *
 * 1000块钱，给定 [2,3,5,50] 问有多少种组合方式，可以重复使用数字
 *
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/18 16:24
 */
public class Arr_钱的组成方式 {


    public static int process(int [] arr, int index,int rest) {

        if (rest < 0 ) {
            return 0;
        }

        if (index == arr.length ) {
            return rest == 0 ? 1 : 0;
        }

        int result = 0;
        for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
            result += process(arr, index + 1,rest - (zhang * arr[index]));
        }
        return result;
    }


    public static int dpway1(int [] arr, int rest){
        int [][] dp = new int[arr.length+1][rest+1];
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                dp[i][j] = -1;
            }
        }
        return process2(arr,0,rest,dp);
    }

    public static int process2(int [] arr, int index,int rest ,int [][] dp) {

        if (rest < 0 ) {
            return 0;
        }

        if(dp[index][rest] != -1){
            return dp[index][rest];
        }

        if (index == arr.length ) {
            if(rest == 0) {dp[index][rest] =1; return 1;
            }else{
                dp[index][rest] =0; return 0;
            }
        }
        int result = 0;
        for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
            result += process(arr, index + 1,rest - (zhang * arr[index]));
        }
        dp[index][rest] = result;
        return result;
    }

    /**
     * 经典动态方程解法，由递归条件可知: dp[index][0] = 1;
     *                  递归顺序从下往上， arr.length 行已经确定,从arr.length-1 开始往上递归
     *                  列递归条件 沿用遍历法的.
     *                  所以 dp[0][aim] 是最终求解结果
     * @param arr
     * @param aim
     * @return
     */
    public static int dpway2(int [] arr,int aim){

        int [][] dp = new int [arr.length+1][aim+1];
        dp[arr.length][0] =1;
        for(int index=arr.length-1;index>=0;index--){
            for(int rest=0;rest<=aim;rest++){
                int result = 0;
                for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
                    result += dp[index + 1][rest - (zhang * arr[index])];
                }
                dp[index][rest] = result;
            }
        }
        return dp[0][aim];
    }

    /**
     *      动态规划进一步优化：省略枚举
     *      观察可知: 每一个 dp[index][rest] 依赖于 dp[index+1][rest - (zhang * arr[index])]
     *                                       那么 dp[index][rest - 1 * arr[index]] 依赖于 dp[index+1][rest -arr[index] - (zhang * arr[index])]
     *                                       所以 dp[index][rest] 依赖于 dp[index+1][rest] + dp[index][rest - arr[index]]
     *
     *                                      图解：假设 第arr[10] = 3;
     *                                      dp[10][97] 依赖 dp[11][1] +.....+dp[11][97]
     *                                      dp[10][94] 依赖 dp[11][1] +.....+dp[11][94]
     *                                      所以: dp[10][97] 依赖 dp[11][97] + dp[10][94];
     *                                      优化遍历过程:
     *                                              dp[index][rest] = dp[index+1][rest];
     *                                              if(rest - (1 * arr[index]) >= 0{
     *                                                  dp[index][rest] += dp[index][rest - arr[index]];
     *                                              }
     *                                dp[10][1].....  dp[10][94]      dp[10][97]
     *                                dp[11][1].....  dp[11][94]      dp[11][97]
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int dpway3(int [] arr,int aim){

        int [][] dp = new int [arr.length+1][aim+1];
        dp[arr.length][0] =1;
        for(int index=arr.length-1;index>=0;index--){
            for(int rest=0;rest<=aim;rest++){
                dp[index][rest] = dp[index+1][rest];
                    if((rest - arr[index]) >= 0){
                        dp[index][rest] += dp[index][rest - arr[index]];
                    }
            }
        }
        return dp[0][aim];
    }


    public static void main(String[] args) {
        int [] arr={5,25,50};
        System.out.println(process(arr,0,50));
        System.out.println(dpway1(arr,50));
        System.out.println(dpway2(arr,50));
        System.out.println(dpway3(arr,50));

    }



}
